package DynamicProgramming.Medium;

public class LC0152 {
    public int maxProduct(int[] nums) {
        int N = nums.length;
        // dpMax[i]表示以i结束的子数组的最大乘积，dpMin[i]表示以i结束的子数组的最小乘积（可能为负）。参与乘法运算的数字必须包括nums[i]。
        int[] dpMax = new int[N], dpMin = new int[N];
        dpMax[0] = dpMin[0] = nums[0];
        for (int i = 1; i < N; i++) {
            int num = nums[i];
            if (num == 0) {
                dpMax[i] = dpMin[i] = 0;
                continue;
            }
            if (num < 0) {
                dpMax[i] = Math.max(num, num * dpMin[i - 1]);
                dpMin[i] = Math.min(num, num * dpMax[i - 1]);
            }
            else {
                dpMax[i] = Math.max(num, num * dpMax[i - 1]);
                dpMin[i] = Math.min(num, num * dpMin[i - 1]);
            }
        }

        int ret = dpMax[0];
        for (int dp : dpMax) {
            ret = Math.max(ret, dp);
        }

        return ret;
    }
}
